package com.local.sort.StraightInsertionSort;

/**直接插入排序
 * ① 思想：最基本的插入排序，将第i个插入到前i-1个中的适当位置。
 * ② 时间复杂度：T(n) = O(n²)。
 * ③ 空间复杂度：S(n) = O(1)。
 * ④ 稳定性：稳定排序。循环条件while(r[0].key < r[j].key)保证的。
 * @author Administrator
 *
 */
public class StraightInsertionSort implements InsertionSort{

	@Override
	public void InsSort(Integer[] array, int start, int end) {
		 /*   
         * 第一层循环：对待插入（排序）的元素进行循环   
         * 从待排序数组断的第二个元素开始循环，到最后一个元素（包括）止   
         */    
        for (int i=start+1; i<=end; i++) {     
            /*   
             * 第二层循环：对有序数组进行循环，且从有序数组最第一个元素开始向后循环   
             * 找到第一个大于待插入的元素   
             * 有序数组初始元素只有一个，且为源数组的第一个元素，一个元素数组总是有序的   
             */    
            for (int j = 0; j < i; j++) {     
                Integer insertedElem = array[i];//待插入到有序数组的元素     
                //从有序数组中最一个元素开始查找第一个大于待插入的元素     
                if ((array[j].compareTo(insertedElem)) > 0) {     
                    //找到插入点后，从插入点开始向后所有元素后移一位     
                    move(array, j, i - 1);     
                    //将待排序元素插入到有序数组中     
                    array[j] = insertedElem;     
                    break;     
                }     
            } 
        }
	}
	
	
	@Override
	public void move(Integer[] array, int startIndex, int endIndex) {
		 for (int i = endIndex; i >= startIndex; i--) {     
	            array[i+1] = array[i];     
	        }
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {

		 Integer[] arr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };  
		 StraightInsertionSort sort = new StraightInsertionSort();
		 sort.InsSort(arr, 0, arr.length-1);
		 for(int i=0; i < arr.length-1; i++) {
			 System.out.print(arr[i]);
		 }
		 System.exit(0);
	}

}
